#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
/*
    RMQ(Range Minimum/Maximum Query, 区间最值问题),
    给定一个长度为 n 的序列，和 m 次查询,
    每次查询返回 [l, r] 中的最大(小)值.
 */

/*
    ST(Sparse Table) 算法
    - O(n*logn)预处理, O(1)单次查询
    - 不支持修改
*/
int dp[100][100];
int rmq(vector<int>& nums, int l, int r) {
    for (int i = 0; i < nums.size(); i++) dp[i][0] = nums[i];
    for (int j = 1; (1 << j) <= nums.size(); j++) {
        for (int i = 0; i + (1 << (j - 1)) < nums.size(); i++) {
            dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
        }
    }
    int k = log2(r - l + 1);
    return max(dp[l][k], dp[r - (1 << k) + 1][k]);
}


/*
    线段树：o（n）预处理，单次查询 logn，可以修改
    树状数组：支持 位置1 到某个点，不支持修改，处理区间和问题
 */


int main() {
    vector<int> nums{1, 2, 6, 8, 4, 3, 7};
    cout << rmq(nums, 1, 4) << endl;
    return 0;
}